// @algorithm @lc id=1307 lang=cpp 
// @title ugly-number-iii


// #define print(...)
// @test(3,2,3,5)=4
// @test(4,2,3,4)=6
// @test(5,2,11,13)=10
// @test(1000000000,2,217983653,336916467)=1999999984
class Solution {
public:
    int nthUglyNumber(int n, int a, int b, int c) {
        long ab = lcm<long>(a,b),
            ac  = lcm<long>(a,c),
            bc  = lcm<long>(b,c),
            abc = lcm<long>(ab, c);
        int left = min({a,b,c}),
            right= min(left*long(n), long(2e9));
        while(left<=right){
            int m = left + (right-left)/2;
            if(n <= m/a+m/b+m/c - m/ab-m/ac-m/bc + m/abc)
                right = m - 1;
            else
                left = m + 1;
        }
        return left;
    }
};